package breakthrough;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;

import game.GameMove;
import game.GamePlayer;
import game.GameState;
import game.Util;

public class GLaDOSBreakthroughPlayer extends RandomBreakthroughPlayer{

	public int DEPTH = 4;
	private int moveNum = 0;
	private long totalGameTime = 0;
	private long moveTime;
	public Heuristic h;
	RandomBreakthroughPlayer randomizeFirstMoves = new RandomBreakthroughPlayer("random");
	
	public GLaDOSBreakthroughPlayer(String sname)
	{
		super(sname);
		h = new Heuristic();
	}
	
	public GLaDOSBreakthroughPlayer(String sname, Heuristic h)
	{
		super(sname);
		this.h = h;
		
	}
	
	public static void moveOrder(BreakthroughState brd, ArrayList<BreakthroughMove> moves)
	{
		ArrayList<BreakthroughMove> tmpMoves = new ArrayList<BreakthroughMove>();
		int size = moves.size();
		for (int i = 0 ; i < size ; i++)
		{
			for (int j = 0 ; j < moves.size() ; j++)
			{
				if (isTake(brd,moves.get(j)))
				{
					tmpMoves.add(moves.get(j));
					moves.remove(j);
				}
			}
			for (int j = 0 ; j < moves.size(); j++)
			{
				tmpMoves.add(moves.get(j));
			}
		}
		moves = tmpMoves;
	}

	public static boolean isTake(BreakthroughState brd, BreakthroughMove move)
	{
		return (brd.board[move.endingRow][move.endingCol] != BreakthroughState.emptySym);
	}
	
	protected ArrayList<BreakthroughMove> getMoveList(GameState state)
	{
		BreakthroughState board = (BreakthroughState)state;
		ArrayList<BreakthroughMove> list = new ArrayList<BreakthroughMove>();  
		BreakthroughMove mv = new BreakthroughMove();
		int dir = state.who == GameState.Who.HOME ? +1 : -1;
		for (int r=0; r<BreakthroughState.N; r++) {
			for (int c=0; c<BreakthroughState.N; c++) {
				mv.startRow = r;
				mv.startCol = c;
				mv.endingRow = r+dir; mv.endingCol = c;
				if (board.moveOK(mv)) {
					list.add((BreakthroughMove)mv.clone());
				}
				mv.endingRow = r+dir; mv.endingCol = c+1;
				if (board.moveOK(mv)) {
					list.add((BreakthroughMove)mv.clone());
				}
				mv.endingRow = r+dir; mv.endingCol = c-1;
				if (board.moveOK(mv)) {
					list.add((BreakthroughMove)mv.clone());
				}
			}
		}
		moveOrder((BreakthroughState)state, list);
		return list;
	}

	protected static void shuffle (ArrayList<BreakthroughMove> ary)
	{
		int len = ary.size();
		for (int i=0; i<len; i++) {
			int spot = Util.randInt(i, len-1);
			BreakthroughMove tmp = ary.get(i);
			ary.set(i,ary.get(spot));
			ary.set(spot,tmp);
		}	
	}	
	
	public double alphabeta(BreakthroughState brd, int depth, double alpha, double beta, boolean toMaximize)
	{
		if (depth == 0 || brd.status != GameState.Status.GAME_ON)
		{
			return h.calc(brd);
		}
		ArrayList<BreakthroughMove> moves = getMoveList(brd);
		shuffle(moves);
		if (toMaximize) // To Maximize
		{
			for (BreakthroughMove move : moves)
			{
				BreakthroughState nBrd = (BreakthroughState) brd.clone();
				nBrd.makeMove(move);
				alpha = Math.max(alpha, alphabeta(nBrd,depth-1,alpha,beta,false));
				if (beta <= alpha)
					break;
			}
			return alpha;
		}
		else // To Minimize
		{
			for (BreakthroughMove move : moves)
			{
				BreakthroughState nBrd = (BreakthroughState) brd.clone();
				nBrd.makeMove(move);
				beta = Math.min(beta, alphabeta(nBrd,depth-1,alpha,beta,true));
				if (beta <= alpha)
					break;
			}
			return beta;
		}
	}
	
	public GameMove getMove(GameState curr, String lastMove)
	{
		
		moveNum++;
			
		moveTime = System.currentTimeMillis();
		ArrayList<BreakthroughMove> moves = getMoveList(curr);
		ArrayList<BreakthroughMove> bestMoves = new ArrayList<BreakthroughMove>();
		BreakthroughMove best = moves.get(0);
		BreakthroughMove finisher = winningMove((BreakthroughState)curr,moves);
		
		if (finisher != null) return finisher;
		if (moveNum < 1) return randomizeFirstMoves.getMove(curr, lastMove);
		
		double bestScore = (curr.who == GameState.Who.HOME) ? Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY;
		for (BreakthroughMove move : moves)
		{
			BreakthroughState nBrd = (BreakthroughState) curr.clone();
			nBrd.makeMove(move);
			double score;
			if (curr.who == GameState.Who.HOME) score = alphabeta(nBrd,DEPTH,bestScore, Double.POSITIVE_INFINITY, true);
			else score = alphabeta(nBrd,DEPTH,Double.NEGATIVE_INFINITY, bestScore, false);
			if (score > bestScore && curr.who  == GameState.Who.HOME)
			{
				bestMoves = new ArrayList<BreakthroughMove>();
				bestMoves.add(move);
				bestScore = score;
				best = move;
			}
			else if (score < bestScore && curr.who == GameState.Who.AWAY)
			{
				bestMoves = new ArrayList<BreakthroughMove>();
				bestMoves.add(move);
				bestScore = score;
				best = move;
			}
			else if (score == bestScore)
			{
				bestMoves.add(move);
			}
		}
		Random rnd = new Random();
		for (BreakthroughMove move : bestMoves)
		{
			BreakthroughState nBrd = (BreakthroughState) curr.clone();
			nBrd.makeMove(move);
//			System.out.print(h.calc(nBrd) + ", ");
		}
//		best = bestMoves.get(rnd.nextInt(bestMoves.size()));
		best = bestMoves.get(0);
		moveTime = System.currentTimeMillis() - moveTime;
		return best;
	}
	
	private BreakthroughMove winningMove(BreakthroughState brd, ArrayList<BreakthroughMove> moves)
	{
		for (BreakthroughMove move : moves)
		{
			BreakthroughState brd2 = (BreakthroughState) brd.clone();
			brd2.makeMove(move);
			if (brd2.status != GameState.Status.GAME_ON) return move;
		}
		return null;
	}
	
	
	
	public static void main(String[] args)
	{
		GamePlayer p = new GLaDOSBreakthroughPlayer("GLaDOS Simple", new Heuristic());
		p.compete(args);
	}
}
